package com.my.leetcode;


import java.util.*;

public class StackProblems {

    public static void main(String[] args) {

        Set<Integer> set = new HashSet<>();
        


        System.out.println(Integer.MAX_VALUE);
        List<String> res = new ArrayList<>();
        for(String s : res){
            System.out.println("-=====");
        }

        /*int [] input = {73, 74, 75, 71, 69, 72, 76, 73};
        int [] res = dailyTemperatures(input);

        for(int i = 0;i < res.length;i++){
            System.out.print(res[i] + "   ");
        }*/
        //System.out.println();
        //System.out.println(Arrays.asList(res).toString());

        StackProblems problems = new StackProblems();
        //System.out.println(problems.calculate("3+2*2"));

        String a = "/zlx/ada/..//./adad";
        String [] as = a.split("/");
        System.out.println(Arrays.toString(as));
       // System.out.println(problems.simplifyPath(a));

        int [] nums1 = {1,3,5,2,4};
        int [] nums2 = {6,5,4,3,2,1,7};
        System.out.println(Arrays.toString(problems.nextGreaterElement(nums1, nums2)));
    }


    /**
     * @author zlx
     * @Description 496. 下一个更大元素 I
     * 给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。
     *
     * 请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。
     *
     * nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。
     *
     *
     *
     * 示例 1:
     *
     * 输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
     * 输出: [-1,3,-1]
     * 解释:
     *     对于 num1 中的数字 4 ，你无法在第二个数组中找到下一个更大的数字，因此输出 -1 。
     *     对于 num1 中的数字 1 ，第二个数组中数字1右边的下一个较大数字是 3 。
     *     对于 num1 中的数字 2 ，第二个数组中没有下一个更大的数字，因此输出 -1 。
     * 示例 2:
     *
     * 输入: nums1 = [2,4], nums2 = [1,2,3,4].
     * 输出: [3,-1]
     * 解释:
     *     对于 num1 中的数字 2 ，第二个数组中的下一个较大数字是 3 。
     *     对于 num1 中的数字 4 ，第二个数组中没有下一个更大的数字，因此输出 -1 。
     *
     *
     * 提示：
     *
     * 1 <= nums1.length <= nums2.length <= 1000
     * 0 <= nums1[i], nums2[i] <= 104
     * nums1和nums2中所有整数 互不相同
     * nums1 中的所有整数同样出现在 nums2 中
     *
     * @Date 4/11/21
     * @Param [nums1, nums2]
     * @return int[]
     **/
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {

        Stack<Integer> stack = new Stack<>();
        Map<Integer, Integer> map = new HashMap<>();
        for(int s2 : nums2){
            while(!stack.isEmpty() && stack.peek() < s2) {
                map.put(stack.pop(), s2);
            }
            stack.push(s2);

        }

        while (!stack.isEmpty()){
            map.put(stack.pop(), -1);
        }

        System.out.println(map);
        int res [] = new int[nums1.length];
        int i = 0;
        for(int s1 : nums1){
            res[i] = map.get(s1);
            i++;
        }
        return res;

    }


    /**
     * @author zlx
     * @Description 简化路径
     * @Date 4/11/21
     * @Param [path]
     * @return java.lang.String
     **/
    public String simplifyPath(String path) {

        Deque<String> stack = new LinkedList<>();
        Set<String> skip = new HashSet<>(Arrays.asList("..",".",""));
        for (String dir : path.split("/")) {
            if (dir.equals("..") && !stack.isEmpty()) stack.pop();
            else if (!skip.contains(dir)) stack.push(dir);
        }
        String res = "";
        for (String dir : stack) res = "/" + dir + res;
        return res.isEmpty() ? "/" : res;
    }

    /**
     * @author zlx
     * @Description 227. 基本计算器 II middle
     * 给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
     *
     * 整数除法仅保留整数部分。
     *
     *
     *
     * 示例 1：
     *
     * 输入：s = "3+2*2"
     * 输出：7
     * 示例 2：
     *
     * 输入：s = " 3/2 "
     * 输出：1
     * 示例 3：
     *
     * 输入：s = " 3+5 / 2 "
     * 输出：5
     *
     *
     * 提示：
     *
     * 1 <= s.length <= 3 * 105
     * s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开
     * s 表示一个 有效表达式
     * 表达式中的所有整数都是非负整数，且在范围 [0, 231 - 1] 内
     * 题目数据保证答案是一个 32-bit 整数
     * @Date 3/29/21
     * @Param [s]
     * @return int
     **/
    public int calculate(String s) {

        s= s.replaceAll(" ", "");
        char [] sArray = s.toCharArray();
        Stack<Integer> stack = new Stack<>();

        for(int i = 0; i< sArray.length;i++){

            Integer tmpVal = 0;
            char tmp = sArray[i];
            if(tmp == ' '){
                continue;
            }else if(Character.isDigit(tmp)){
                tmpVal = tmp - '0';
                int j;
                for(j = i+1;j < sArray.length;j++){
                    if(Character.isDigit(sArray[j])){
                        tmpVal = tmpVal * 10 + (sArray[j] - '0');
                    }else{
                        break;
                    }
                }
                if(i - 1 < 0){
                    stack.push(tmpVal);
                }
                else{
                    if(sArray[i-1] == '+'){
                        stack.push(tmpVal);
                    }else if(sArray[i-1] == '-'){
                        stack.push(-tmpVal);
                    }else {
                        stack.push(calculate(tmpVal, stack.pop(), sArray[i-1]));
                    }
                }
                i = j;

            }
        }

        System.out.println(stack);
        int res = 0;
        while(!stack.isEmpty()){
            res += stack.pop();
        }
        return res;
    }

    public int calculate(int tmpVal, int peekVal, char flag){

        if(flag == '*'){
            System.out.println("======="+ tmpVal * peekVal);
            return tmpVal * peekVal;
        }else{
            return peekVal / tmpVal;
        }
    }


    /**
     * @author zlx
     * @Description 1124. 表现良好的最长时间段 middle
     * 给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数。
     *
     * 我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。
     *
     * 所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。
     *
     * 请你返回「表现良好时间段」的最大长度。
     *
     *
     *
     * 示例 1：
     *
     * 输入：hours = [9,9,6,0,6,6,9]
     * 输出：3
     * 解释：最长的表现良好时间段是 [9,9,6]。
     *
     *
     * 提示：
     *
     * 1 <= hours.length <= 10000
     * 0 <= hours[i] <= 16
     *
     * 解题思路： 将大于8的置为1， 小于8的置为-1， 根据题意直接简化为求连续子串和大于1的子串长度；
     * 基于单调递减栈求解
     *
     *
     *
     * @Date 2020-12-15
     * @Param [hours]
     * @return int
     **/
    public int longestWPI(int[] hours) {

        for(int i = 0;i < hours.length;i++){
            hours[i] = hours[i] > 8 ? 1 : -1;
        }

        int [] score = new int[hours.length + 1];
        for(int i = 0;i < hours.length;i++){
            score[i + 1] = score[i] + hours[i];
        }

        //构建单调递减栈
        Stack<Integer> stack = new Stack<>();
        for(int i = 0;i < hours.length;i++){
            if(!stack.isEmpty() && score[stack.peek()] <= score[i]){
                continue;
            }else{
                stack.push(i);
            }
        }
        System.out.println("stack is:=====" + stack);

        int ans = 0;
        for(int i = score.length - 1;i >= 0;i--){
            if(score[i] > score[stack.peek()]){
                ans = Math.max(ans, i - stack.peek());
                stack.pop();
                i++;
                if(stack.isEmpty()){
                    break;
                }
            }
        }
        return ans;
    }



    public boolean backspaceCompare(String S, String T) {

        String s = getString(S);
        String t = getString(T);
        return s.equals(t);


    }

    public String getString(String S){

        Stack<Character> s = new Stack<>();
        for(int i = 0;i < S.length();i++){

            char c = S.charAt(i);
            if(c == '#' && !s.isEmpty()){
                s.pop();
            }else{
                s.push(c);
            }
        }
        String res = "";
        while (!s.isEmpty()){
            res = s.pop() + res;
        }
        return res;
    }


    /**
     * @author zlx
     * @Description 402. 移掉K位数字  middle
     * 给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。
     *
     * 注意:
     *
     * num 的长度小于 10002 且 ≥ k。
     * num 不会包含任何前导零。
     * 示例 1 :
     *
     * 输入: num = "1432219", k = 3
     * 输出: "1219"
     * 解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。
     * 示例 2 :
     *
     * 输入: num = "10200", k = 1
     * 输出: "200"
     * 解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
     * 示例 3 :
     *
     * 输入: num = "10", k = 2
     * 输出: "0"
     * 解释: 从原数字移除所有的数字，剩余为空就是0。
     *
     * 解题思路： 移除k位数字，使得剩下的数字最小，表示字符串中的数组相对顺序保持不变，123a234 123b234, 若a<b, 数字123a234 < 123b234,
     * 遍历字符串， 当nums[i] < nums[i-1] , 将nums[i-1] 移除， 否则放入到stack栈中， 最后取占中len - k 个元素
     *
     * @Date 2020-09-24
     * @Param [num, k]
     * @return java.lang.String
     **/
    public String removeKdigits(String num, int k) {

        if(num == null || num.length() == 0 || k <= 0){
            return num;
        }
        int len = num.length() - k;
        Stack<Integer> stack = new Stack<>();

        for(int i = 0;i < num.length();i++){

            Integer c = num.charAt(i) - '0';
            while (!stack.isEmpty() && k >= 1 && stack.peek() > c){
                stack.pop();
                k--;
            }
            stack.push(c);
        }

        Integer [] arrays = stack.toArray(new Integer [stack.size()]);
        System.out.println(Arrays.toString(arrays));
        StringBuilder sb = new StringBuilder();
        for(int i = 0;i < len;i++){
            sb.append(arrays[i]);
        }
        String res = sb.toString();
        res = res.replaceAll("^0*", "");
        return res.length() == 0 ? "0" : res;

    }

    /**
     * @author zlx
     * @Description 946. 验证栈序列
     * 给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。
     *
     *
     *
     * 示例 1：
     *
     * 输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
     * 输出：true
     * 解释：我们可以按以下顺序执行：
     * push(1), push(2), push(3), push(4), pop() -> 4,
     * push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
     * 示例 2：
     *
     * 输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
     * 输出：false
     * 解释：1 不能在 2 之前弹出。
     *
     *
     * 提示：
     *
     * 0 <= pushed.length == popped.length <= 1000
     * 0 <= pushed[i], popped[i] < 1000
     * pushed 是 popped 的排列。
     *
     * 解题思路： 基于栈进行求解，pushed数据放到stack中，当栈定元素和popped相等，则出栈， 最后判断stack是否为空，空true
     * @Date 2020-07-14
     * @Param [pushed, popped]
     * @return boolean
     **/
    public boolean validateStackSequences(int[] pushed, int[] popped) {

        if(pushed.length != popped.length){
            return false;
        }

        int index = 0;
        Stack<Integer> stack = new Stack<>();
        for(int i = 0;i < pushed.length;i++){
            stack.push(pushed[i]);
            while (!stack.isEmpty() && stack.peek() == popped[index]){
                stack.pop();
                index++;
            }
        }
        if(stack.isEmpty()){
            return true;
        }
        return false;
    }


    /**
     * 739. 每日温度
     *
     * 根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。
     *
     * 例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
     *
     * 提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。
     *
     * 解题思路： 利用栈进行求解，
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/daily-temperatures
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param T
     * @return
     */
    public static int[] dailyTemperatures(int[] T) {

        int [] res = new int[T.length];
        //存储下标
        Stack<Integer> stack = new Stack<>();
        for(int i = 0;i < T.length;i++){
            while (!stack.isEmpty() && T[stack.peek()] < T[i]){
                int tmp = stack.pop();
                res[tmp] = i - tmp;
            }
            stack.push(i);
        }
        return res;
    }

}
